import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 17655
 * Date: 2025-06-11
 * Time: 21:20
 */
public class test4 {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> ret = new ArrayList<Integer>();
        Stack<TreeNode> s1 = new Stack<TreeNode>();
        while(root!=null || !s1.isEmpty()){
            while(root!=null){
                s1.push(root);
                root = root.left;
            }
            root = s1.pop();
            ret.add(root.val);
            root = root.right;
        }
        return ret;
    }


    class TreeNode{
        TreeNode left;
        TreeNode right;
        int val;

        TreeNode(){

        }

        TreeNode(int val){
            this.val = val;
        }

        TreeNode(int val, TreeNode right, TreeNode left){
            this.val = val;
            this.right = right;
            this.left = left;
        }
    }
}
